package com.hy.greedy;

import java.util.Arrays;

public class NonOverlappingSpace {


    /**
     * 435. 无重叠区间
     * 力扣题目链接
     *
     * 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
     *
     * 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
     *
     * 示例 1:
     *
     * 输入: [ [1,2], [2,3], [3,4], [1,3] ]
     * 输出: 1
     * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
     *
     * 示例 3:
     *
     * 输入: [ [1,2], [2,3] ]
     * 输出: 0
     * 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
     *
     * 思路
     * 相信很多同学看到这道题目都冥冥之中感觉要排序，但是究竟是按照右边界排序，还是按照左边界排序呢？
     *
     * 我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
     *
     * 此时问题就是要求非交叉区间的最大个数。
     *
     * 右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。
     *
     * 局部最优推出全局最优，试试贪心！
     *
     * @param num
     * @return
     */


    public int nonOverLappingSpace(int [][] num){
        // 按照区间右边界升序排序
        Arrays.sort(num,(x,y)->{return x[1] - y[1];});

        int count = 0;
        // 上个区域的右边界
        int edge = Integer.MIN_VALUE;
        for (int i = 0; i < num.length; i++) {
            // 若上一个区间的右边界小于当前区间的左边界，说明无交集
            if (edge <= num[i][0]){
                edge = num[i][1];
            }else {
                count ++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int [][] num = { {1,2}, {2,3}, {3,4}, {1,3}};
        NonOverlappingSpace nonOverlappingSpace = new NonOverlappingSpace();

        System.out.println("res: "+nonOverlappingSpace.nonOverLappingSpace(num));

    }
}
